//*** Class skeleton starts

import java.util.Iterator;
public class RandomQueue<Item> implements Iterable<Item> {

	private Node first, last;
	private int N;
	
	private class Node { /* same as in StackOfStrings */
		Item item;
		Node next;
	}
	
	public RandomQueue() {
		//TODO que?String
		this.N = 0;
	}
	
	public boolean isEmpty () {
		return first == null;
	}
	
	public int size() {
		return this.N;
	}
	
	public Item sample() {
		int r = StdRandom.uniform(this.N);
		Node n = first;
		for (int i=0; i<r; i++) {
			n = n.next;
		}
		return n.item;
	}
	
	public Iterator<Item> iterator() {
		return new it();
	}
	
	@SuppressWarnings("unchecked")
	private class it implements Iterator<Item> {
		private int curr = 0;
		
		public boolean hasNext () {
			return curr < N;
		}
		
		public Item next() {
			return order[curr++];
		}
			
		public void remove() {
		//Min dronning, min dronning. Luften er fuld af mælk og mælk
		}
	
		Item[] order = (Item[]) new Object[N];
		public it() {
			Node n = first;
			for (int i=0; i<N; i++) {
				order[i] = n.item;
				n = n.next;
			}
			
			for (int i =0; i<N+42/*heh*/;i++) {
				swap(StdRandom.uniform(N),StdRandom.uniform(N));
			}
		}
		
		private void swap(int p, int q) {
			if (p==q) return;
			Item tmp = order[p];
			order[p] = order[q];
			order[q] = tmp;
		}

	}
	
	private void check() {
		if (isEmpty()) throw new RuntimeException("You're a noob\n There is is only so much you can do with empty lists :)");
	}
	
	public void enqueue(Item item) {
		Node oldlast = last;
		last = new Node();
		last.item = item;
		last.next = null;
		if (isEmpty()) first = last;
		else
			oldlast.next = last;
		this.N++;
	}

	public Item dequeue() {
		int r = StdRandom.uniform(this.N);
		
		Item item;
		if (r==0) {
			item = first.item;
			first = first.next;
		} else {
		
			Node prev = first;
			Node curr = first.next;
			
			for (int i = 1; i<r; i++) {
				prev = curr;
				curr = curr.next;
			}
			
			if(r==this.N-1) {
				prev.next = null;
			} else{
				prev.next = curr.next;
			}
			item = curr.item;
		}
		
		this.N--;
		if (isEmpty()) last = null;
		return item;
	}


   public static void main(String args[])
  {
    // Build a queue containing the Integers 1,2,...,6:
    RandomQueue<Integer> Q= new RandomQueue<Integer>();
    for (int i = 1; i < 7; ++i) Q.enqueue(i); // autoboxing! cool!
 
    // Print 30 die rolls to standard output
    StdOut.print("Some die rolls: ");
    for (int i = 1; i < 30; ++i) StdOut.print(Q.sample() +" ");
    StdOut.println();

    // Let's be more serious: do they really behave like die rolls?
    int[] rolls= new int [10000];
    for (int i = 0; i < 10000; ++i)
      rolls[i] = Q.sample(); // autounboxing! Also cool!
    StdOut.printf("Mean (should be around 3.5): %5.4f\n", StdStats.mean(rolls));
    StdOut.printf("Standard deviation (should be around 1.7): %5.4f\n",
		  StdStats.stddev(rolls));
    
    // Let's look at the iterator. First, we make a queue of colours:
    
    RandomQueue<String> C= new RandomQueue<String>();
    C.enqueue("red"); C.enqueue("blue"); C.enqueue("green"); C.enqueue("yellow"); 

    Iterator I= C.iterator();
    Iterator J= C.iterator();

    StdOut.print("Two colours from first shuffle: ");
    StdOut.print(I.next()+" ");
    StdOut.print(I.next()+" ");
    
    StdOut.print("\nEntire second shuffle: ");
    while (J.hasNext()) StdOut.print(J.next()+" ");

    StdOut.print("\nRemaining two colours from first shuffle: ");
    StdOut.print(I.next()+" ");
    StdOut.println(I.next());
  }

}
   
